When a packet communication network becomes congested, ports that supply packets through the communications infrastructure can end up dropping one or more packets in a stream. This can result in errors at the receive end of a connection. In some networks, however, when a single packet is dropped an entire block of packets may be resent in order to recover from the error. Resending all of the packets in a block in order to recover a single or a few dropped packets adds more traffic and can make the congestion worse.
At the same time, packet traffic is often bursty in that for short time packets will arrive at a port very quickly, then no packets or only a few packets will arrive. In many cases, this busty pattern is caused by typical user behavior. An Internet browser, for example, might select to view a web page causing a server to send all of the packets necessary to transfer the web page. The user then views the web page after it is received and makes no requests for a time.
To take advantage of this typical traffic pattern, traffic is throttled at some ports so that during busy periods traffic is buffered and packets are sent at a slower rate than is requested. The extra packets continue to be sent during a normally quiet period until all of the buffers are emptied. This type of throttling requires choices to be made between packets that are urgent or higher priority and those that are less urgent or lower priority. It also requires a scheduler to reduce the rate at which packets are applied to the port in order to prevent any from being dropped. There are many different approaches to scheduling which try to determine which packets should be sent first.
A Round-Robin (RR) and Weighted-Round-Robin (WRR) scheduler picks packets based on a weight assigned to a channel. Bandwidth share is maintained according to weights. Decisions are made on the basis of packets.
RR scheduling is used to maintain the relative shares among channels in both non-congested and congested conditions. However, it does not assign a fixed-rate to a channel. This allows any subscriber to use as much bandwidth as is available. Weights can be assigned to channels to give channels different levels of relative shares.
A Deficit-Round-Robin (DRR) scheduler runs in rounds based on a fixed time interval. A channel is added by a certain number of credits or counts in each round. The current number of credits of a channel is the same as the number of bytes or bits the channel is eligible to send. The scheduler picks packets from channels that have enough credits to cover the size of the packet. Traffic is measured in units of bits or bytes rather than in packets, thus DRR maintains fairness bandwidth among channels on the basis of bits-per-second. In contrast, RR and WRR maintain fairness among channels on the basis of the number-of-packets.
With credit-based systems, channels are refilled with credits as time goes by. This changes the round-robin behavior from packet-based scheduling to bandwidth-based scheduling. This also gives the ability for service providers to cap subscriber bandwidths to fixed amounts.
Generalized Process Sharing (GPS), Weighted-Fair-Queuing (WFQ), Worst-Case-Fair-Weighted-Fair-Queuing (WF2Q) are all based on DRR, and are bit-based algorithms.
Reservation-based GCRA (Generic Cell Rate Algorithm) is an ATM (Asynchronous Transfer Mode) formula provided by the ATM Forum Traffic Management version 4.0. This has been approximated using a scoreboard to perform scheduling. Since, in ATM, all the packets are fixed-size cells, a credit unit on the scoreboard can be degenerated to a one-bit number. The scoreboard uses one bit to keep a schedule of sending cells for a channel. With this hardware scoreboard based scheduling, the effect of WRR is achieved.
The problem with the scoreboard is that multiple channels can compete for a single timeslot. The GCRA describes the rate of single channel based on shaping/policing parameters. It therefore seeks to maintain a maximum-minimum fairness, that is, to give low-demand channels (e.g. 1.5M channels) an advantage over high-demand channels (e.g. 6M channels) under congestion. As a result, under congestion, the high-paying customers receive the same amount of bandwidth as all other customers. The max-min fairness makes proportional fairness impossible.